{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### heapq 模块\n",
    "\n",
    "Python 的 heapq 模块使用列表实现堆操作，与许多其他模块不同，heapq 模块不定义自定义类，但定义了直接处理列表的函数。\n",
    "\n",
    "Python 的 heapq 模块实现的是**最小堆**，符合以下特征：\n",
    "\n",
    "- 每个父节点的值都小于或等于其子节点的值。\n",
    "\n",
    "- 堆在内存中通常通过数组来实现，满足以下关系：\n",
    "\n",
    "- 对于任意一个节点 k，有 heap[k] <= heap[2 * k + 1] 和 heap[k] <= heap[2 * k + 2]。这样可以快速找到堆中的最小元素：总是在根节点 heap[0]。\n",
    "\n",
    "由于使用数组实现，使得堆的操作（如插入和删除）效率高，时间复杂度都为O(log n)（其中n是堆中元素的数量）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 堆操作\n",
    "\n",
    "- 使用列表 heap ，然后调用 heapq.heapify(heap) 将列表 heap 转换为堆。\n",
    "\n",
    "- 调用 heappush(heap, item) 函数将元素 item 插入到堆 heap 中，保持堆的性质。\n",
    "\n",
    "- 调用 heapq.heappop(heap) 弹出并返回堆 heap 中最小的元素，同时保持堆的性质。如果堆为空会抛出 IndexError。\n",
    "\n",
    "- 调用 heappushpop(heap, item) 将元素 item 插入堆 heap 中并弹出最小的元素。这个组合操作比先调用 heappush 然后 heappop 更有效率。\n",
    "\n",
    "- 调用 heapreplace(heap, item) 在弹出最小元素的同时将 item 插入堆 heap 中，堆的大小不变。此函数也是在堆为空时会引发 IndexError。它的作用是将堆中最小的元素弹出，并将新元素 item 添加到堆中。如果堆为空，无法执行此操作。\n",
    "\n",
    "- nlargest() 和 nsmallest() 这两个函数可用于返回可迭代对象中最大的或最小的n个元素。\n",
    "\n",
    "- heapq.merge(*iterables) 用于合并多个已排序的输入为一个已排序的输出。它返回一个迭代器，适合于处理大量数据时节省内存。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 6, 5, 8, 7]\n",
      "1\n",
      "[2, 5, 3, 6, 7, 8, 4]\n",
      "0\n",
      "[2, 5, 3, 6, 7, 8, 4]\n",
      "2\n",
      "[3, 5, 4, 6, 7, 8, 9]\n",
      "[9, 8]\n",
      "[3, 4]\n",
      "[1, 2, 4, 5, 7, 8]\n"
     ]
    }
   ],
   "source": [
    "import heapq\n",
    "heap = [3, 2, 1, 6, 5, 8, 7]\n",
    "heapq.heapify(heap)\n",
    "print(heap)\n",
    " \n",
    "rs = heapq.heappop(heap)\n",
    "print(rs)\n",
    " \n",
    "heapq.heappush(heap, 4)\n",
    "print(heap)\n",
    "\n",
    "rs = heapq.heappushpop(heap, 0)\n",
    "print(rs)\n",
    "print(heap)\n",
    "\n",
    "rs = heapq.heapreplace(heap, 9)\n",
    "print(rs)\n",
    "print(heap)\n",
    "\n",
    "largest_two = heapq.nlargest(2, heap)\n",
    "smallest_two = heapq.nsmallest(2, heap)\n",
    "print(largest_two)\n",
    "print(smallest_two) \n",
    "\n",
    "iter1 = [1, 4, 7]\n",
    "iter2 = [2, 5, 8]\n",
    "merged = heapq.merge(iter1, iter2)\n",
    "print(list(merged))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
